package binarysearchtree;

/**
 * @Author liangzai
 * @Description:
 */
public class BinarySearchTree {
    TreeNode root;

    public void insert(int val){
        if(root == null){
            root = new TreeNode(val);
            return ;
        }
        TreeNode parent = null;
        TreeNode pcur = root;
        TreeNode node = new TreeNode(val);
        while (pcur != null) {
            if (val > pcur.val) {
                parent = pcur;
                pcur = pcur.right;
            }else if (val < pcur.val) {
                parent = pcur;
                pcur = pcur.left;
            }else{
                return;
            }
        }
        if (val > parent.val) {
            parent.right = node;
        }else {
            parent.left = node;
        }
    }

    public TreeNode search(int val){
        TreeNode pcur = root;
        while (pcur != null) {
            if (val > pcur.val) {
                pcur = pcur.right;
            } else if (val < pcur.val) {
                pcur = pcur.left;
            }else {
                return pcur;
            }
        }
        return null;
    }

    public void remove(int val){
        TreeNode parent = null;
        TreeNode child = root;
        while (child.val != val) {
            if (val > child.val) {
                parent = child;
                child = child.right;
            }else if (val < child.val) {
                parent = child;
                child = child.left;
            }else {
                break;
            }
        }
        removeChild(child ,parent);
        return ;
    }

    private void removeChild(TreeNode child,TreeNode parent){
        if(child.left==null){
            if (child == root) {
                root = child.right;
            } else if (parent.right == child) {
                parent.right = child.right;
            }else {
                parent.left = child.right;
            }
        } else if (child.right == null) {
            if (child == root) {
                root = child.left;
            } else if (parent.right == child) {
                parent.right = child.left;
            }else {
                parent.left = child.left;
            }
        }else {
            TreeNode tp = child.right;
            TreeNode t = tp.left;
            while (t!=null && t.left != null) {
                tp = t;
                t = t.left;
            }
            if (t == null) {
                child.val = tp.val;
                child.right = tp.right;
                return ;
            }
            child.val = t.val;
            tp.left = t.right;
        }
    }
}
